package problems.daily;

import utils.beans.TreeNode;

import java.util.Stack;

/**
 * 105. 从前序和中序遍历序列构造二叉树
 *
 * @author habitplus
 * @version 1.0
 * @history create by guan at 2024/2/20 21:01
 */
public class DT105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length < 1 || preorder.length != inorder.length) {
            return null;
        }

        int n = preorder.length;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        int inorderIndex = 0;

        stack.push(root);
        for (int i = 1; i < n; ++i) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    ++inorderIndex;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }

        return root;
    }
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length < 1 || preorder.length != inorder.length) {
            return null;
        }

        int n = preorder.length;
        int[] map = new int[6001];

        for (int i = 0; i < n; ++i) {
            map[inorder[i] + 3000] = i;
        }

        return buildTree(preorder, map, 0, 0, n - 1);
    }

    /**
     * 根据前序序列和中序序列的映射关系构建二叉树。
     *
     * @param preorder 前序序列
     * @param map 中序序列与原始数组下标的映射关系（中序序列元素在原始数组中的下标+3000）
     * @param k 当前处理的前序序列元素的索引
     * @param l 当前子树的中序序列起始位置
     * @param r 当前子树的中序序列结束位置
     * @return 构建的二叉树的根节点
     */
    private TreeNode buildTree(int[] preorder, int[] map, int k, int l, int r) {
        if (l > r || k >= preorder.length || k < 0) {
            return null;
        }

        int inorderIndex = map[preorder[k] + 3000];
        int cnt = inorderIndex - l;
        TreeNode root = new TreeNode(preorder[k]);
        // 递归构建左子树
        root.left = buildTree(preorder, map, k + 1, l, inorderIndex - 1);
        // 递归构建右子树
        root.right = buildTree(preorder, map, k + cnt + 1, inorderIndex + 1, r);
        return root;
    }
}
